#include <iostream>

/* run this program using the console pauser or add your own getch, system("pause") or input loop */

typedef struct LinkNode {
	int data;
	LinkNode *next;
};

/**
* 时间复杂度为：O(M*N)
*/
void func1(LinkNode *ha, LinkNode *hb, LinkNode *&hc) {
	LinkNode *pa = ha->next, *pb = hb->next, *pc, *cur;
	hc = (LinkNode*)malloc(sizeof(LinkNode));
	cur = hc;

	while (pa != nullptr) {
		pc = (LinkNode*)malloc(sizeof(LinkNode));
		pc->data = pa->data;
		cur->next = pc;
		cur = pc;
		pa = pa->next;
	}

	while (pb != nullptr) {
		pa = ha->next;
		while (pa != nullptr && pa->data != pb->data) {
			pa = pa->next;
		}
		if (pa == nullptr) {
			pc = (LinkNode*)malloc(sizeof(LinkNode));
			pc->data = pb->data;
			cur->next = pc;
			cur = pc;
		}
		pb = pb->next;
	}
	cur->next = nullptr;
}

/**
* 时间复杂度为：O(M+N)
*/
void func2((LinkNode *ha, LinkNode *hb, LinkNode *&hc) {
	LinkNode *pa = ha->next, *pb = hb->next, *pc, *cur;
	hc = (LinkNode*)malloc(sizeof(LinkNode));
	cur = hc;

	while (pa != nullptr && pb != nullptr) {
		if (pa->data < pb->data) {
			pc = (LinkNode*)malloc(sizeof(LinkNode));
			pc->data = pa->data;
			cur->next = pc;
			cur = pc;
			pa = pa->next;
		} else if (pa->data > pb->data) {
			pc = (LinkNode*)malloc(sizeof(LinkNode));
			pc->data = pb->data;
			cur->next = pc;
			cur = pc;
			pb = pb->next;
		} else {
			pc = (LinkNode*)malloc(sizeof(LinkNode));
			pc->data = pa->data;
			cur->next = pc;
			cur = pc;
			pa = pa->next;
			pb = pb->next;
		}
	}

	if (pb != nullptr) {
		pa = pb;
	}

	while (pa != nullptr) {
		pc = (LinkNode*)malloc(sizeof(LinkNode));
		pc->data = pa->data;
		cur->next = pc;
		cur = pc;
		pa = pa->next;
	}
	
	cur->next = nullptr;
}

int main(int argc, char** argv) {
	return 0;
}